﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CSLearn
{
    public class Greedy
    {

        /// <summary>
        /// leetcode  2789  合并后数组中的最大元素
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public long MaxArrayValue(int[] nums)
        {
            long res = nums[nums.Length - 1];
            for (int i = nums.Length - 2; i >= 0; i--)
            {
                res = res >= nums[i] ? res + nums[i] : nums[i];
            }
            return res;
        }

        /// <summary>
        /// leetcode  2673  使二叉树所有路径值相等的最小代价(贪心)
        /// </summary>
        /// <param name="n"></param>
        /// <param name="cost"></param>
        /// <returns></returns>
        public int MinIncrements(int n, int[] cost)
        {
            int res = 0;
            for (int i = n - 2; i > 0; i -= 2)
            {
                res += Math.Abs(cost[i] - cost[i + 1]);
                cost[i / 2] += Math.Max(cost[i], cost[i + 1]);
            }

            return res;
        }

        /// <summary>
        /// leetcode  1465  切割后面积最大的蛋糕(贪心)
        /// </summary>
        /// <param name="h"></param>
        /// <param name="w"></param>
        /// <param name="horizontalCuts"></param>
        /// <param name="verticalCuts"></param>
        /// <returns></returns>
        public int MaxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts)
        {
            Array.Sort(horizontalCuts);
            Array.Sort(verticalCuts);
            return (int)((long)GetMax(horizontalCuts, h) * GetMax(verticalCuts, w));
        }

        int GetMax(int[] array, int board)
        {
            int res = 0, pre = 0;
            foreach (int item in array)
            {
                res = Math.Max(item - pre, res);
                pre = item;
            }
            return Math.Max(board - pre, res);
        }

        /// <summary>
        /// leetcode  1402  做菜顺序(贪心)
        /// </summary>
        /// <param name="satisfaction"></param>
        /// <returns></returns>
        public int MaxSatisfaction(int[] satisfaction)
        {
            Array.Sort(satisfaction, (a, b) => b - a);
            int preSum = 0, res = 0;
            foreach (var item in satisfaction)
            {
                if (preSum + item > 0)
                {
                    preSum += item;
                    res += preSum;
                }
                else
                    break;
            }
            return res;
        }

        /// <summary>
        /// leetcode  56  合并区间(贪心)
        /// </summary>
        /// <param name="intervals"></param>
        /// <returns></returns>
        public int[][] Merge(int[][] intervals)
        {
            if (intervals.Length <= 1) return intervals;

            List<int[]> res = new List<int[]>();
            Array.Sort(intervals, (a, b) => a[0] - b[0]);

            int left = intervals[0][0];
            int right = intervals[0][1];
            for (int i = 1; i < intervals.Length; i++)
            {
                if (right < intervals[i][0])
                {
                    res.Add(new int[] { left, right });
                    left = intervals[i][0];
                    right = intervals[i][1];
                }
                else
                {
                    left = Math.Min(left, intervals[i][0]);
                    right = Math.Max(right, intervals[i][1]);
                }
            }
            res.Add(new int[] { left, right });

            return res.ToArray();
        }

        /// <summary>
        /// leetcode  738  单调递增的数字(贪心)
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public int MonotoneIncreasingDigits(int n)
        {
            char[] str = n.ToString().ToCharArray();
            int length = str.Length;
            int flag = length;
            for (int i = length - 1; i > 0; i--)
            {
                if (str[i] < str[i - 1])
                {
                    str[i - 1]--;
                    flag = i;
                }
            }
            for (int i = flag; i < length; i++)
            {
                str[i] = '9';
            }
            return Convert.ToInt32(new string(str));
        }

        /// <summary>
        /// leetcode  763  划分字母区间(贪心)
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public IList<int> PartitionLabels(string s)
        {
            IList<int> res = new List<int>();
            int[] endIndex = new int[26];
            int n = s.Length;

            for (int i = 0; i < n; i++)
            {
                endIndex[s[i] - 'a'] = i;
            }

            int index = 0;
            int last = -1;
            for (int i = 0; i < n; i++)
            {
                index = Math.Max(index, endIndex[s[i] - 'a']);
                if (i == index)
                {
                    res.Add(i - last);
                    last = i;
                }
            }
            return res;
        }

        /// <summary>
        /// leetcode  435  无重叠区间(贪心)
        /// </summary>
        /// <param name="intervals"></param>
        /// <returns></returns>
        public int EraseOverlapIntervals(int[][] intervals)
        {
            Array.Sort(intervals, (a, b) => a[0] - b[0]);

            int n = intervals.Length;
            int count = 1;
            for (int i = 1; i < n; i++)
            {
                if (intervals[i][0] < intervals[i - 1][1])
                {
                    intervals[i][1] = Math.Min(intervals[i - 1][1], intervals[i][1]);
                }
                else
                    count++;
            }

            return n - count;
        }

        /// <summary>
        /// leetcode  452  用最少数量的箭引爆气球(贪心)
        /// </summary>
        /// <param name="points"></param>
        /// <returns></returns>
        public int FindMinArrowShots(int[][] points)
        {
            int n = points.Length;
            Array.Sort(points, (a, b) => (int)(((long)a[0] - b[0]) % int.MaxValue));

            int count = 1;
            for (int i = 1; i < n; i++)
            {
                if (points[i][0] > points[i - 1][1])
                    count++;
                else
                    points[i][1] = Math.Min(points[i - 1][1], points[i][1]);
            }

            return count;
        }

        /// <summary>
        /// leetcode  2591  将钱分给最多的儿童(贪心)
        /// </summary>
        /// <param name="money"></param>
        /// <param name="children"></param>
        /// <returns></returns>
        public int DistMoney(int money, int children)
        {
            if (money < children) return -1;
            money -= children;
            int count = Math.Min(money / 7, children);
            money -= count * 7;
            children -= count;
            if ((children == 0 && money > 0) || (children == 1 && money == 3))
                count--;

            return count;
        }

        /// <summary>
        /// leetcode  406  根据身高重建队列(贪心)
        /// </summary>
        /// <param name="people"></param>
        /// <returns></returns>
        public int[][] ReconstructQueue(int[][] people)
        {
            List<int[]> res = new List<int[]>();
            int n = people.Length;
            Array.Sort(people, (a, b) =>
            {
                if (a[0] == b[0]) return a[1] - b[1];
                return b[0] - a[0];
            });

            foreach (int[] p in people)
            {
                res.Insert(p[1], p);
            }
            return res.ToArray();
        }

        /// <summary>
        /// leetcode  860  柠檬水找零(贪心)
        /// </summary>
        /// <param name="bills"></param>
        /// <returns></returns>
        public bool LemonadeChange(int[] bills)
        {
            int five = 0;
            int ten = 0;
            for (int i = 0; i < bills.Length; i++)
            {
                switch (bills[i])
                {
                    case 5:
                        five++;
                        break;
                    case 10:
                        ten++;
                        five--;
                        break;
                    case 20:
                        if (ten > 0)
                        {
                            ten--;
                            five--;
                        }
                        else
                            five -= 3;
                        break;
                    default:
                        break;
                }
                if (ten < 0 || five < 0)
                    return false;
            }
            return true;
        }

        /// <summary>
        /// leetcode  135  分发糖果(贪心)
        /// </summary>
        /// <param name="ratings"></param>
        /// <returns></returns>
        public int Candy(int[] ratings)
        {
            int n = ratings.Length;
            if (n == 1) return 1;

            int res = 0;
            int[] candies = new int[n];
            candies[0] = 1;
            for (int i = 1; i < n; i++)
            {
                candies[i] = (ratings[i - 1] < ratings[i]) ? (candies[i - 1] + 1) : 1;
            }
            for (int i = n - 1; i > 0; i--)
            {
                if (ratings[i - 1] > ratings[i])
                    candies[i - 1] = Math.Max(candies[i] + 1, candies[i - 1]);
            }
            foreach (int num in candies)
            {
                res += num;
            }
            return res;
        }

        /// <summary>
        /// leetcode  134  加油站(贪心)
        /// </summary>
        /// <param name="gas"></param>
        /// <param name="cost"></param>
        /// <returns></returns>
        public int CanCompleteCircuit(int[] gas, int[] cost)
        {
            int curSum = 0;
            int totalSum = 0;
            int start = 0;
            int n = gas.Length;
            for (int i = 0; i < n; i++)
            {
                int rest = gas[i] - cost[i];
                curSum += rest;
                totalSum += rest;
                if (curSum < 0)
                {
                    start = i + 1;
                    curSum = 0;
                }
            }
            if (totalSum < 0) return -1;

            return start;
        }

        /// <summary>
        /// leetcode  1005  K次取反后最大化的数组和
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public int LargestSumAfterKNegations(int[] nums, int k)
        {
            int n = nums.Length;
            Array.Sort(nums, (x, y) => Math.Abs(y) - Math.Abs(x));
            int res = 0;
            for (int i = 0; i < n; i++)
            {
                if (k > 0)
                {
                    if (nums[i] < 0)
                    {
                        nums[i] = -nums[i];
                        k--;
                    }
                }
                res += nums[i];
            }
            if (k % 2 == 1)
            {
                nums[n - 1] = -nums[n - 1];
                res += 2 * nums[n - 1];
            }
            return res;
        }

        /// <summary>
        /// leetcode  122  买卖股票的最佳时机2(贪心)
        /// </summary>
        /// <param name="prices"></param>
        /// <returns></returns>
        public int MaxProfit(int[] prices)
        {
            int n = prices.Length;
            if (n <= 1) return 0;
            int res = 0;
            for (int i = 1; i < prices.Length; i++)
            {
                res += Math.Max(prices[i] - prices[i - 1], 0);
            }
            return res;
        }


        /// <summary>
        /// leetcode  53  最大子数组和
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public int MaxSubArray(int[] nums)
        {
            int res = int.MinValue;
            int count = 0;
            for (int i = 0; i < nums.Length; i++)
            {
                count += nums[i];
                if (count > res)
                    res = count;
                else if (count < 0)
                    count = 0;
            }
            return res;
        }

        /// <summary>
        /// leetcode  376  摆动序列(贪心)
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public int WiggleMaxLength(int[] nums)
        {
            int n = nums.Length;
            if (n == 1)
            {
                return 1;
            }
            if (n == 2)
            {
                if (nums[0] == nums[1])
                    return 1;
                else
                    return 2;
            }
            int maxLength = 1;
            int curDiff = 0;
            int preDiff = 0;
            for (int i = 1; i < n; i++)
            {
                curDiff = nums[i] - nums[i - 1];
                if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0))
                {
                    maxLength++;
                    preDiff = curDiff;
                }
            }
            return maxLength;
        }

        /// <summary>
        /// leetcode  455  分发饼干(贪心)
        /// </summary>
        /// <param name="g"></param>
        /// <param name="s"></param>
        /// <returns></returns>
        public int FindContentChildren(int[] g, int[] s)
        {
            int count = 0;
            Array.Sort(g);
            Array.Sort(s);
            for (int i = 0; i < s.Length && count < g.Length; i++)
            {
                if (s[i] >= g[count])
                {
                    count++;
                }
            }

            return count;
        }

        /// <summary>
        /// leetcode  45  跳跃游戏2(贪心)
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public int Jump(int[] nums)
        {
            int count = 0;
            int max = 0;
            int cur = 0;
            for (int i = 0; i <= max && max < nums.Length - 1; i++)
            {
                cur = Math.Max(i + nums[i], cur);
                if (i == max)
                {
                    max = cur;
                    count++;
                }
            }
            return count;
        }

        /// <summary>
        /// leetcode  55  跳跃游戏(贪心)
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public bool CanJump(int[] nums)
        {
            if (nums.Length == 1) return true;
            int max = 0;
            for (int i = 0; i <= max; i++)
            {
                max = Math.Max(i + nums[i], max);
                if (max >= nums.Length - 1) return true;
            }
            return false;
        }

    }
}
